'''
什么是归并排序？
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
作为一种典型的分而治之思想的算法应用，归并排序的实现由两种方法：
1、自上而下的递归
2、自下而上的迭代

'''

# 自上而下的递归
def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

def merge(left, right):
    result = []
    while left and right:
        if left[0] <= right[0]:
            result.append(left.pop(0))
        else:
            result.append(right.pop(0))
    while left:
        result.append(left.pop(0))
    while right:
        result.append(right.pop(0))
    return result

# 示例
arr = [64, 25, 12, 22, 11]
sorted_arr = merge_sort(arr)
print(sorted_arr)




# 自下而上的迭代
def merge_sort_down(arr):
    if len(arr) <= 1:
        return arr
    n = len(arr)
    size = 1
    while size < n:
        left = 0
        while left < n:
            mid = left + size - 1
            right = min(left + 2 * size - 1, n - 1)
            merge2(arr, left, mid, right)
            left += 2 * size
        size *= 2
    return arr


# 合并两个有序子数组
def merge2(arr, left, mid, right):
    # 创建左右子数组的临时副本
    left_temp = arr[left:mid + 1]
    right_temp = arr[mid + 1:right + 1]

    i = j = 0  # 左右子数组的索引
    k = left  # 合并后数组的索引

    # 合并两个有序子数组
    while i < len(left_temp) and j < len(right_temp):
        if left_temp[i] <= right_temp[j]:
            arr[k] = left_temp[i]
            i += 1
        else:
            arr[k] = right_temp[j]
            j += 1
        k += 1

    # 复制剩余元素
    while i < len(left_temp):
        arr[k] = left_temp[i]
        i += 1
        k += 1
    while j < len(right_temp):
        arr[k] = right_temp[j]
        j += 1
        k += 1


# 示例
arr = [64, 25, 12, 22, 11]
sorted_arr = merge_sort_down(arr)
print(sorted_arr)
